package com.zql.LeetCode;

import java.util.HashSet;
import java.util.Set;

/**
 * Created By ShuHua on 2021/8/21.
 */
public class CarPooling_1094 {
    /**
     * 以车站数作为差分数组的数量，【2，1，5】就是在1到4的区间全部+2，如果最后数组中有元素的值超过capacity就说明不行
     * 对应差分数组就是下标为1的位置+2，下标为6的位置-2,如果最后差分数组叠加的过程中出现叠加值大于容量capacity则返回false
     * @param trips
     * @param capacity
     * @return
     */
    public static boolean carPooling(int[][] trips, int capacity) {
        //初始化差分数组,长度设为1000以上 因为题目要求 ：0 <= trips[i][1] < trips[i][2] <= 1000
        int[] diff = new int[1010];
        int realCount=0;
        for(int i=0;i<trips.length;i++){
            int inNums =trips[i][0];
            int onCar = trips[i][1];
            int offcar = trips[i][2];
            diff[onCar] += inNums;
            diff[offcar] -=inNums;
        }
        //这里设置好的差分数组就相当于每个站点的上下车人数
        //判断是否超载的条件：我们从第一个站点开始叠加，如果叠加的过程中出现实际上车数大于capacity，则超载；否则没有超载
        for(Integer i : diff){
            realCount+=i;
            if(realCount>capacity){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int a[][] = {{3,2,8},{4,4,6},{10,8,9}};
        System.out.println("Result:"+carPooling(a,11));
    }
}
